//这里将写一些排序算法
#include <stdio.h>
#include <time.h>
//1.插入排序
//1.从第一个元素开始，该元素可以认为已经被排序
//2.取下一个元素tem，从已排序的元素序列从后往前扫描
//3.如果该元素大于tem，则将该元素移到下一位
//4.重复步骤3，直到找到已排序元素中小于等于tem的元素
//5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
//6.重复步骤2~5
void add_sort(int *arr,int n)
{
    int i=0;
    //进行n-1趟
    for(i=0;i<n-1;i++)
    {
        int end=i;

        int tem=arr[end+1];//这是我们要插入的元素
        while(end>=0)
        {
            if(tem<arr[end])
            {
                arr[end+1]=arr[end];
                end--;
            }
            else
            break;
        }
        //跳出来循环时
        arr[end+1]=tem;
    }
}
//希尔排序
//1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，
//并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
//2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
void shell_sort(int *arr,int n)
{
    //第一增量gap
    int gap=n;
    while(gap>1)
    {
        //每次对gap折半操作
        gap/=2;
        int i=0;
        for(i=0;i<n-gap;i++)
        {
            int end=i;
            //锁定插入对象
            int tem=arr[end+gap];
            while(end>=0)
            {
                if(tem<arr[end])
                {
                    arr[end+gap]=arr[end];
                    end-=gap;
                }
                else
                break;
            }
            arr[end+gap]=tem;
        }
    }
}
//选择排序
//每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
//实际上，我们可以一趟选出两个值，一个最大值一个最小值，
//然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
// void choose_sort(int *arr, int n)
// {

// }
int main()
{
    int arr[]={8,7,9,3,2,5,6,0,1,4,4};
    int n=sizeof(arr)/sizeof(arr[0]);
    add_sort(arr,n);

   
    int i=0;
    for(i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}

